package SwordOffer;

import java.util.HashSet;
import java.util.Set;

public class Sword_Offer_13 {

    private Set<Integer> set;
    private int k, m, n;
    private int[][] directs = new int[][]{{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
    public int movingCount(int m, int n, int k) {
        set = new HashSet<>();
        this.k = k;
        this.m = m;
        this.n = n;
        dps(0, 0);
        return set.size();
    }

    private void dps(int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return;
        }
        if (mod(i) + mod(j) > k) {
            return;
        }
        int v = i * 200 + j;
        if (!set.contains(v)) {
            set.add(v);
            for (int[] direct : directs) {
                dps(i + direct[0], j + direct[1]);
            }
        }
    }

    private int mod(int val) {
        int sum = 0;
        while (val > 0) {
            sum += (val % 10);
            val /= 10;
        }
        return sum;
    }

    public static void main(String[] args) {
        Sword_Offer_13 model = new Sword_Offer_13();
        System.out.println(model.movingCount(1, 1, 0));
    }
}
